//将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 
//
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 
//
// 示例: 
//
// 给定有序数组: [-10,-3,0,5,9],
//
//一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
//
//      0
//     / \
//   -3   9
//   /   /
// -10  5
// 
// Related Topics 树 深度优先搜索 
// 👍 541 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：将有序数组转换为二叉搜索树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P108_ConvertSortedArrayToBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new P108_ConvertSortedArrayToBinarySearchTree().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * DFS
     */
    class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return sortedArrayToBST(nums, 0, nums.length - 1);
        }

        private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
            if (left > right) {
                return null;
            }
            // 取数组中间靠左的值作为根节点
            int middle = (left + right) / 2;
            TreeNode root = new TreeNode(nums[middle]);
            root.left = sortedArrayToBST(nums, left, middle - 1);
            root.right = sortedArrayToBST(nums, middle + 1, right);
            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
